Binary Tree Maximum Path Sum || Binary Tree Postorder Traversal

发表于

Binary Tree Maximum Path Sum

Question

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:

Given the below binary tree,

1
2
3
  1
 / \
2   3

Return 6.

Analysis

中文题解

如上述题解所说的，最后的路径可能有四种情况：

  1. 只有node
  2. node+leftsub
  3. node+rightsub
  4. node+leftsub+rightsub

故在计算的过程中，假如left/right=0，则可得1-3种情况的值，若均不为0，则为第4种情况，同时与已经记录的maxvalue进行大小比较确定师傅需要更新。

由于路径不能回退的特性，所以返回值是right，left的最大值加上当前的val

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int maxvalue;
    public int maxPathSum(TreeNode root) {
        maxvalue=Integer.MIN_VALUE;
        maxPath(root);
        return maxvalue;
    }
    
    public int maxPath(TreeNode root){
        if(root==null)  return 0;
        int left=Math.max(0,maxPath(root.left));
        int right=Math.max(0,maxPath(root.right));
        maxvalue=Math.max(maxvalue,left+right+root.val);
        return Math.max(left,right)+root.val;
    }
}

Binary Tree Postorder Traversal

Question

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:

Given binary tree {1,#,2,3},

1
2
3
4
5
1
 \
  2
 /
3

return [3,2,1].

Analysis

正常的递归后续遍历

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        helper(root,result);
        return result;
    }
    
    private void helper(TreeNode root, List<Integer> result){
        if(root==null)  return;
        helper(root.left,result);
        helper(root.right,result);
        result.add(root.val);
        return;
    }
}